# 给你两个字符串
# haystack 和 needle ，请你在 haystack 字符串中找出
# needle 字符串的第一个匹配项的下标（下标从
# 0 开始）。如果#needle 不是 haystack
# 的一部分，则返回 - 1 。
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        n=len(haystack)
        m=len(needle)
        for i in range(n-m+1):#因为要满足i+m-1<n
            if haystack[i:i+m]==needle:
                return i
        return -1
solution=Solution()
haystack = "sadbutsad"
needle = "sad"
print(solution.strStr(haystack,needle))